package leetcode.剑指offer.剑指II;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/10 20:28
 * @description：https://leetcode-cn.com/problems/4sjJUc/
 */
public class 剑指_II_82_含有重复元素集合的组合 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum2(new int[]{1, 2, 7, 6, 1, 5}, 8));
    }

    class Solution {
        boolean vis[];

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            this.vis = new boolean[candidates.length];
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(candidates);
            backtrack(candidates, ans, new ArrayList<>(), target, 0);
            return ans;
        }

        private void backtrack(int[] candidates, List<List<Integer>> ans, ArrayList<Integer> list, int target, int idx) {
            if (target == 0) {
                ans.add(new ArrayList<>(list));
                return;
            }
            for (int i = idx; i < candidates.length; i++) {
                if (vis[i] || i > 0 && candidates[i] == candidates[i - 1] && !vis[i - 1]) continue;
                if (target - candidates[i] >= 0) {
                    list.add(candidates[i]);
                    vis[i] = true;
                    backtrack(candidates, ans, list, target - candidates[i], i + 1);
                    list.remove(list.size() - 1);
                    vis[i] = false;
                }
            }
        }
    }
}
